package leetcode;

import java.util.Arrays;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0037.java
 * @Author : WangRuoyu
 * @Date 2023/11/3 22:01
 */


public class Q0037 {
    boolean[][] stx = new boolean[9][10];
    boolean[][] sty = new boolean[9][10];
    boolean[][] stn = new boolean[9][10];
    boolean flag = false;

    public void dfs(int k, char[][] board) {
        if (k == 81) {
            flag = true;
            return;
        }
        int x = k / 9;
        int y = k % 9;
        int n = (x / 3) * 3 + y / 3;
        if (board[x][y] != '.') {
            dfs(k + 1, board);
        } else {
            for (int i = 1; i <= 9; i++) {
                if (!stx[x][i] && !sty[y][i] && !stn[n][i]) {
                    stx[x][i] = true;
                    sty[y][i] = true;
                    stn[n][i] = true;
                    board[x][y] = (char) ('0' + i);
                    dfs(k + 1, board);
                    if (flag) {
                        break;
                    }
                    stx[x][i] = false;
                    sty[y][i] = false;
                    stn[n][i] = false;
                    board[x][y] = '.';
                }
            }
        }
    }

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '0';
                stx[i][num] = true;
                sty[j][num] = true;
                stn[(i / 3) * 3 + j / 3][num] = true;
            }
        }
        dfs(0, board);
        for (int i = 0; i < board.length; i++) {
            System.out.println(Arrays.toString(board[i]));
        }
    }

    public static void main(String[] args) {
        Q0037 sl = new Q0037();
        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        sl.solveSudoku(board);
    }
}
